/*
给定一个非空的字符串s，检查是否可以通过由它的一个子串重复多次构成
*/

/* 用滑动窗口 */
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define SIZE 2

bool repeatedSubstringPattern(char *s) 
{
    int len = strlen(s);
    for (int idx = 1; idx <= len / SIZE; ++idx) 
    {
        if (len % idx == 0) 
        {
            char pattern[idx + 1]; // 声明一个长度为 i+1 的字符数组，用于存储子串
            strncpy(pattern, s, idx); // 将 s 的前 i 个字符复制到 pattern 中
            pattern[idx] = '\0'; // 在 pattern 的末尾添加字符串结束符
            int jdx = idx;
            while (jdx< len) 
            {
                if (strncmp(s + jdx, pattern, idx) != 0) 
                { // 比较 s 中以 j 为起始位置的子串与 pattern 是否相同
                    break;
                }
                jdx += idx; // 更新 j 的值，准备比较下一个子串
            }
            if (jdx == len) 
            {
                return true; // 如果 j 等于 n，说明整个字符串都可以由重复的子串构成，返回 true
            }
        }
    }
    return false; // 如果没有找到符合条件的子串，返回 false
}



///当然，除了上面提供的方法之外，还有一种基于 KMP 算法的解决方案
//来检查一个字符串是否可以由重复的子串构成。下面是一个使用 KMP 算法的 C 语言示例代码：


#include <stdio.h>
#include <string.h>
#include <stdbool.h>

// 计算字符串的最长公共前后缀数组
void computeLPSArray(char *pat, int M, int *lps) 
{
    int len = 0;
    lps[0] = 0; // lps[0] 总是 0

    int idx = 1;
    while (idx < M) 
    {
        if (pat[idx] == pat[len]) 
        {
            len++;
            lps[idx] = len;
            idx++;
        } 
        else 
        {
            if (len != 0) 
            {
                len = lps[len - 1];
            } 
            else 
            {
                lps[idx] = 0;
                idx++;
            }
        }
    }
}

bool repeatedSubstringPattern(char *s) 
{
    int n = strlen(s);
    if (n <= 1) 
    {
        return false;
    }

    int lps[n];
    computeLPSArray(s, n, lps);

    int len = lps[n - 1];
    return len > 0 && n % (n - len) == 0;
}